package com.zql.LeetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created By ShuHua on 2021/10/22.
 */

/**
 *
 * 第一步：扩大窗口范围，直到窗口内包含t的所有字符
 * 第二步：停止扩大窗口，缩小串口找到窗口内只有t中字符的子串
 * 重复二三，直到right==s.length
 */
public class FindAnagrams_438 {
    public static List<Integer> findAnagrams(String s, String t){
        List<Integer> list = new ArrayList<>();

        Map<Character,Integer> need = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();

        for(char c: t.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }

        int right = 0;
        int left = 0;
        int valid=0;
        char[] s1 =s.toCharArray();
        while (right<s.length()){
            char c = s1[right];
            right++;
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if(need.get(c).equals(window.get(c)))valid++;
            }

            while (valid==need.size()){
                if(right-left==t.length()) list.add(left);
                char c1 = s1[left];
                left++;
                if(need.containsKey(c1)){
                    if(need.get(c1).equals(window.get(c1))) valid--;
                    window.put(c1,window.get(c1)-1);

                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        String s = "cbaebabacd";
        String t = "ab";
        List<Integer> list = findAnagrams(s,t);
        for (Integer integer : list) {
            System.out.println(integer);
        }

    }
}
